/* 
 * trapping rain water
 * for example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6
 */

#include "../../func.h"

int trap1(vector<int> &A)
{
    const int n = A.size();
    int *maxLeft = new int[n]();
    int *maxRight = new int[n]();

    for (int i = 1; i < n; ++i)
    {
        maxLeft[i] = max(maxLeft[i - 1], A[i - 1]);
        maxRight[n - 1 - i] = max(maxRight[n - i], A[n - i]);
    }

    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        int height = min(maxLeft[i], maxRight[i]);
        if (height > A[i])
        {
            sum += height - A[i];
        }
    }

    delete[] maxLeft;
    delete[] maxRight;
    return sum;
}

int trap2(vector<int> &A)
{
    const int n = A.size();
    int max = 0;
    for (int i = 0; i < n; ++i)
    {
        if (A[i] > A[max])
            max = i;
    }

    int water = 0;
    for (int i = 0, peak = 0; i < max; ++i)
    {
        if (A[i] > peak)
            peak = A[i];
        else
            water += peak - A[i];
    }
    for (int i = n - 1, top = 0; i > max; --i)
    {
        if (A[i] > top)
            top = A[i];
        else
            water += top - A[i];
    }
    return water;
}